package study.datastructure.order.sort.test;

import java.util.Arrays;

public class MergeSort {
    public static void main(String[] args) {
        int[] arr = {38, 27, 43, 3, 9, 82, 10};
        mergeSort(arr, 0, arr.length - 1);
        System.out.println(Arrays.toString(arr)); // 输出排序结果
    }

    // 归并排序递归函数
    public static void mergeSort(int[] arr, int left, int right) {
        if (left < right) {
            int mid = left + (right - left) / 2; // 避免整数溢出
            mergeSort(arr, left, mid);      // 递归排序左半部分
            mergeSort(arr, mid + 1, right); // 递归排序右半部分
            merge(arr, left, mid, right);   // 合并两个有序数组
        }
    }

    // 合并函数（核心难点）
    private static void merge(int[] arr, int left, int mid, int right) {
        // 创建两个临时数组，存储左右子数组的内容
        int[] leftArr = Arrays.copyOfRange(arr, left, mid + 1);
        int[] rightArr = Arrays.copyOfRange(arr, mid + 1, right + 1);

        int i = 0, j = 0; // i遍历leftArr，j遍历rightArr
        int k = left;     // k从原数组的left位置开始填充

        // 比较两个子数组的元素，按顺序合并
        while (i < leftArr.length && j < rightArr.length) {
            if (leftArr[i] <= rightArr[j]) {
                arr[k++] = leftArr[i++];
            } else {
                arr[k++] = rightArr[j++];
            }
        }

        // 处理剩余元素（只有一边可能有剩余）
        while (i < leftArr.length) {
            arr[k++] = leftArr[i++];
        }
        while (j < rightArr.length) {
            arr[k++] = rightArr[j++];
        }
    }
}